/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package pathfinder;

import java.io.*;
import java.util.ArrayList;
import java.util.*;
import java.net.URL;

/**
 *
 * @author Christian Aastrup
 */
public class Pathfinder {
    
private Tile[][] arrayTiles2D;
private PathfinderTile[][] arrayPFTiles2D;
private static byte DIRECTION_NORTH = 1;
private static byte DIRECTION_EAST = 2;
private static byte DIRECTION_SOUTH = 4;
private static byte DIRECTION_WEST = 8;

    public Pathfinder()
    {
        setTileTraversabilityFromFile("traversability.txt");
        //setTileTraversability();
        setPathFinderTielTraversability();
        //testPerformanceMethod();
        //outputTraversability();
        //debugArrayListChecker();
        //calculateOptimalPaths();
        calculateOptimalPathsBetter();
        //compareTileDirections();
        //debugTestExecutionTimeOfContainsAndByte();
    }
    
    public Tile[][] getTilesWithTraversability()
    {
        return arrayTiles2D;
    }
    
    private void testPerformanceMethod()
    {
        
        byte[][] array2D = new byte[40][40];
        boolean[][] array2DBoolean = new boolean[40][40];
        ArrayList<Integer> al = new ArrayList<Integer>();
        
        for(int j = 0; j < 30; j++)
        {
            int temp = (int) (Math.random() * 100);
            al.add(temp);
        }
        
        
        long startArray = System.currentTimeMillis();
        for(int i = 0; i < 9000; i++)
        {
            array2D = new byte[40][40];
            for(int y = 0; y < array2D.length; y++)
            {
                for(int x = 0; x < array2D[0].length; x++)
                {
                    int posX = (int)(Math.random() * 40);
                    //int posY = (int)(Math.random() * 40);
                    //int randNumb = (int) (Math.random() * 50);
                    boolean b = al.contains(5);
                }
            }
                
        }
        System.out.println("2D array: time: " + (System.currentTimeMillis() - startArray));
        List<Boolean> l = new ArrayList<Boolean>(Collections.nCopies(6400, false));
        long startArrayList = System.currentTimeMillis();
        
        
        for(int n = 0; n < 9000; n++)
        {
            //array2DBoolean = new boolean[40][40][4];
            
            ArrayList<Boolean> al2 = new ArrayList<Boolean>(6400);
            al2.addAll(l);
            
            for(int y = 0; y < array2D.length; y++)
            {
                for(int x = 0; x < array2D[0].length; x++)
                {
                    int posX = (int)(Math.random() * 40);
                    //int posY = (int)(Math.random() * 40);
                    //int randNumb = (int) (Math.random() * 50);
                    boolean b = array2DBoolean[posX][y];
                    //array2DBoolean[posX][posY][2] = true;
                }
            }       
           
        }
        System.out.println("2D boolean: time: " + (System.currentTimeMillis() - startArrayList));
        
        
        
    }
    
    private void compareTileDirections()
    {
        System.out.println("Direction for 0,11 14,14 " + arrayTiles2D[0][11].getDirectionForDestination(14,14));
        System.out.println("Direction for 0,0 to 4,1 " + arrayTiles2D[0][0].getDirectionForDestination(4,1));
        System.out.println("Direction for 0,0 to 4,9 " + arrayTiles2D[0][0].getDirectionForDestination(4,9));
    }
    
    private void setPathFinderTielTraversability()
    {
        arrayPFTiles2D = new PathfinderTile[arrayTiles2D.length][arrayTiles2D[0].length];
        
        for(int i = 0; i < arrayTiles2D.length; i++)
        {       
            
            for(int n = 0; n < arrayTiles2D[i].length; n++)
            {
                if(arrayTiles2D[i][n].isTraversable() == true)
                {
                    arrayPFTiles2D[i][n] = new PathfinderTile(true);
                }
                
                else
                {
                    arrayPFTiles2D[i][n] = new PathfinderTile(false);
                }
            }
            
        }
    }
    
    private void setTileTraversabilityFromFile(String fileName)
    {
        ArrayList<String> alTraversabilityInString = new ArrayList<String>();
        
        try
		{
                    URL url = getClass().getResource( fileName);
                    
            
		    // open stream
                    //InputStream resStream = Pathfinder.class.getClass().getResourceAsStream(fileName);
		    //fileInputStreamWithTraversability = new FileInputStream(fileName);

		    //DataInputStream inputstream = new DataInputStream(fileInputStreamWithTraversability);
                    //BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(resStream));
                    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader( url.openStream() ) );
                    String line;
                    //read file
                    while ((line = bufferedReader.readLine()) != null)   
                    {
                        alTraversabilityInString.add(line);
                    }

		    // close
		    //fileInputStreamWithTraversability.close();		
		}

		catch (Exception e)
		{
			System.err.println ("unable to read file");
		}
        
        arrayTiles2D = new Tile[alTraversabilityInString.size()][alTraversabilityInString.size()];
        
        for(int y = 0; y < alTraversabilityInString.size(); y++)
        {
            //System.out.println("");
            for(int n = 0, x = 0; n < alTraversabilityInString.get(y).length() - 1; n += 3, x++)
            {
                //String s = alTraversabilityInString.get(i).;
                String s = alTraversabilityInString.get(y).substring(n, n+2);
                //System.out.print(s);
                
                if(s.equals("RR"))
                {
                    arrayTiles2D[x][y] = new Tile(true, arrayTiles2D.length, arrayTiles2D[0].length);
                }
                else if(s.equals("00"))
                {
                    arrayTiles2D[x][y] = new Tile(false, arrayTiles2D.length, arrayTiles2D[0].length);
                }
                else
                {
                    assert false : "Traversability file not formatted correctly";
                    System.out.println("Traversability file not formatted correctly");
                }
            }
        }
    }
    
    
    
    private void outputTraversability()
    {
        System.out.println("Output Traversability: ");
        System.out.print(" " + arrayTiles2D[0][0].isTraversable());
        System.out.print(" " + arrayTiles2D[0][1].isTraversable());
        System.out.print(" " + arrayTiles2D[0][2].isTraversable());
        System.out.print(" " + arrayTiles2D[0][3].isTraversable());
        System.out.print(" " + arrayTiles2D[0][4].isTraversable());
        System.out.print(" " + arrayTiles2D[0][5].isTraversable());
        System.out.print(" " + arrayTiles2D[0][6].isTraversable());
        System.out.print(" " + arrayTiles2D[0][7].isTraversable());
        System.out.print(" " + arrayTiles2D[0][8].isTraversable());
        System.out.print(" " + arrayTiles2D[0][9].isTraversable());
        System.out.print(" " + arrayTiles2D[0][10].isTraversable());
        System.out.print(" " + arrayTiles2D[0][11].isTraversable());
        System.out.print(" " + arrayTiles2D[0][12].isTraversable());
        System.out.print(" " + arrayTiles2D[0][13].isTraversable());
        System.out.println(" " + arrayTiles2D[0][14].isTraversable());
        
        
        
        
        for(int border = 0; border < arrayTiles2D.length; border++)
        {
            System.out.print("#");
        }
        System.out.println("##");
        
        for(int y = 0; y < arrayTiles2D.length; y++)
        {
            System.out.print("#");
            for(int x = 0; x < arrayTiles2D[y].length; x++)
            {
                if(arrayTiles2D[x][y].isTraversable())
                {
                    System.out.print("O");
                }
                else
                {
                    System.out.print("#");
                }
            }
            System.out.println("#");
           
            
        }
        for(int border = 0; border < arrayTiles2D.length; border++)
        {
            System.out.print("#");
        }
        System.out.println("##");
    }
    
    
    
    
    
    private boolean byteContainsNorth(int by)
    {
        if(by == 15 || by == 13 || by == 11 || by == 9 || by == 7 || by == 5 || by == 3 || by == 1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsEast(int by)
    {
        if(by == 15 || by == 14 || by == 11 || by == 10 || by == 7 || by == 6 || by == 3 ||  by == 2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsSouth(int by)
    {
        if(by == 15 || by == 14 || by == 13 || by == 12 || by == 7 || by == 6 || by == 5 || by == 4)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private boolean byteContainsWest(int by)
    {
        if(by == 15 || by == 14 || by == 13 || by == 12 || by == 11 || by == 10 || by == 9 ||  by == 8)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private void doPrePathing()
    {
        
    }
    
    private void calculateOptimalPathsBetter()
    {
        int numberOfRows = arrayPFTiles2D.length;
        int numberOfColumns = arrayPFTiles2D[0].length;
        byte[][] prePathingArray2D = new byte[numberOfRows][numberOfColumns]; 
        int numberOfTiles = 1;
        int numberOfDestinationTiles = 1;
        
        //PRE PATHING init
        for(int prePathingY = 0; prePathingY < numberOfColumns; prePathingY++)
        {
           for(int prePathingX = 0; prePathingX < numberOfRows; prePathingX++)
           {
               prePathingArray2D[prePathingX][prePathingY] = 0;
           }
                    
        }
        
        // PRE PATHING
        for(int prePathingY = 0; prePathingY < numberOfColumns; prePathingY++)
        {
           for(int prePathingX = 0; prePathingX < numberOfRows; prePathingX++)
           {              
               if(prePathingY == 0) // can not move NORTH because the north tile is outside board
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_NORTH;
               }
               if(prePathingY == numberOfColumns - 1) // can not move SOUTH because tile is outside board
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_SOUTH;
               }
               
               if(prePathingX == 0) // can not move WEST
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_WEST;
               }
               
               if(prePathingX == numberOfRows - 1) // can not move EAST
               {
                   prePathingArray2D[prePathingX][prePathingY] += Pathfinder.DIRECTION_EAST;
               }
               
               if(!(arrayTiles2D[prePathingX][prePathingY].isTraversable())) // if current tile is not traversable
               {
                   //north
                    if(!(prePathingY == 0)) // make sure there is a north tile
                    {
                        prePathingArray2D[prePathingX][prePathingY - 1] += Pathfinder.DIRECTION_SOUTH;
                    }
                    
                   //east
                    if(!(prePathingX == numberOfRows - 1)) 
                    {
                        prePathingArray2D[prePathingX + 1][prePathingY] += Pathfinder.DIRECTION_WEST;
                    }
                    
                   //south
                    if(!(prePathingY == numberOfColumns - 1)) // make sure there is a south tile
                    {
                        prePathingArray2D[prePathingX][prePathingY + 1] += Pathfinder.DIRECTION_NORTH;
                    }
                   //west
                    if(!(prePathingX == 0)) // make sure there is a west tile
                    {
                        prePathingArray2D[prePathingX - 1][prePathingY] += Pathfinder.DIRECTION_EAST;
                    }
               }
               
               
               
               
           }
                    
        }
        

        
        byte[][] directionsNotValid = new byte[numberOfRows][numberOfColumns]; // create an array where the directions are not valid
        // happens when either the destination or the origin is not valid
        
        for(int dnvY = 0; dnvY < numberOfColumns; dnvY++)
        {
            for(int dnvX = 0; dnvX < numberOfRows; dnvX++)
            {
                directionsNotValid[dnvX][dnvY] = -1;
            }
        }
        
        for(int y = 0; y < numberOfColumns; y++) // Loop through all the (columns)tiles to find the optimal path
        {
            for(int x = 0; x < numberOfRows; x++) // Loop through all the rows to find the optimal path
            {
                if(arrayTiles2D[x][y].isTraversable() == false) // checks if the starting tile is even traversable
                {
                    //System.out.println("Tile: " + x + "," + y + " is not traversable, skipping");
                    arrayTiles2D[x][y].setDestinations(directionsNotValid);
                    continue;
                }
                long startTime1TileAllDests = System.currentTimeMillis();
                PathfinderTile startingPathFindertile = arrayPFTiles2D[x][y];
                byte[][] directionsToDestination = new byte[numberOfRows][numberOfColumns];
                
                for(int destinationY = 0; destinationY < numberOfColumns; destinationY++) // find the optimal path to all the tiles on the board for the current tile
                {
                    for(int destinationX = 0; destinationX < numberOfRows; destinationX++)
                    { 
                        //long startTime1Tile1Dest = System.currentTimeMillis();
                        if(arrayTiles2D[destinationX][destinationY].isTraversable() == false)
                        {
                            directionsToDestination[destinationX][destinationY] = -1;
                            //System.out.println("Destination not traversable");
                            continue;
                        }
                        if(destinationX == x && destinationY == y) // if the destination is the same as the starting tile
                        {
                            directionsToDestination[destinationX][destinationY] = -1; // set all directions to -1
                            //System.out.println("Starting and destination tile same");
                            continue;
                            
                        }
                        
                        long startTime = System.currentTimeMillis();
                        
                        PathfinderTile destinationPathFindertile = arrayPFTiles2D[destinationX][destinationY]; // change later
                        PathfinderTile currentPathFindertile = startingPathFindertile;
                        int stepsInCurrentOptimalPath = 999999; // number of steps in the best possible path, is set to a high number so that steps will always be lower at first
                        byte firstDirection = 0;
                        byte firstDirectionInOptimalPath = 0; // the first direction (N/E/S/W) of the path that leads to the destination
                        boolean isUniquePathsLeft = true; // if false it means there are no possibly paths left to traversed
                        
                        /* holds an array with the directions which are not allowed,
                         *  e.g. 3 = 1 + 2, where 1 = north and 2 = east --> north and east not allowed 
                         */
                        byte[][] pathingArray2D = new byte[numberOfRows][numberOfColumns]; // array with the directions which are NOT allowed, these are added as the tiles are being traversed
                        int[][] pathingNumberOfSteps2D = new int[numberOfRows][numberOfColumns]; // holds another pathing array with the number of steps to a tile
                       
                        
                        
                        
                        
                    
                        
                        /*
                        for(int copyarrayY = 0; copyarrayY < prePathingArray2D[0].length; copyarrayY++)  // copies the array, the array must be copied
                        {
                            for(int copyarrayX = 0; copyarrayX < prePathingArray2D.length; copyarrayX++)
                            {
                                pathingArray2D[copyarrayX][copyarrayY] = prePathingArray2D[copyarrayX][copyarrayY];
                            }
                        }
                         * */
   
                        for(int n = 0; isUniquePathsLeft == true; n++) // Loop through all the paths for 1 tile and 1 destination
                        {
                            boolean deadEndFound = false; // gets changed to true if a dead end is run --> new path
                            boolean pathFound = false; // gets changed to true if a path to the destination is found --> new path
                            int currentPosX = x; // starting pos X, this changes as the path runs
                            int currentPosY = y; // starting pos Y, this changes as the path runs since it also represents the current position
                            
                       
                            boolean[][] pathingTilesTraversed = new boolean[numberOfRows][numberOfColumns];

                       
                            //variable change/methods
                            //alTraversedTiles.add(arrayPFTiles2D[currentPosX][currentPosY]);
                            pathingTilesTraversed[currentPosX][currentPosY] = true; // boolean array with a list of tiles traversed this path, 1 = traversed this turn, 0 = not traversed
                            byte lastDirectionTraveled = 0;
                       
                       for(int numberOfSteps = 0;deadEndFound == false && pathFound == false;) // loop through 1 path
                       {
                           assert (pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]) < 16 : "ERROR: pathing at exceeded 15, a direction has been added more than"; // if has exceeded 15 then one direction has been added more than once
                           //System.out.println("avail: " + pathingArray2D[currentPosX][currentPosY]);
                           //System.out.println("east: " + pathingTilesTraversed[currentPosX + 1][currentPosY]);
                           
                           if(numberOfSteps > (stepsInCurrentOptimalPath)) // check if number of steps we've taken has exceeded the number of steps in the current best path that has reached dest
                           {
                               pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;
                                    
                               deadEndFound = true;
                               continue;
                           }

                           
                           

                            // try to move NORTH
                           boolean isNorthAvailable = !(byteContainsNorth( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isNorthAvailable) // checks if the north tile is available
                            {
                                if( (numberOfSteps + 1) < pathingNumberOfSteps2D[currentPosX][currentPosY - 1] || pathingNumberOfSteps2D[currentPosX][currentPosY - 1] == 0) // check if has gone this way before AND this path has a fewer number of steps
                                {
                                    //PathfinderTile northTile = arrayPFTiles2D[currentPosX][currentPosY - 1];
                                    
                                    if( !pathingTilesTraversed[currentPosX][currentPosY - 1] ) // check if has traversed this tile this turn
                                    {
                                        //System.out.println("Moved North, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY + " " + currentPosX + "," + currentPosY + " numberOfSteps: " + pathingNumberOfSteps2D[10][3]);
          
                                        currentPosY -= 1;        
                                        numberOfSteps++;
                                        lastDirectionTraveled = 1;

                                        currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                        pathingTilesTraversed[currentPosX][currentPosY] = true;
                                        //alTraversedTiles.add(currentPathFindertile);

                                        if(numberOfSteps == 1)
                                        {
                                            firstDirection = lastDirectionTraveled;
                                        }

                                        if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                        {
                                            pathFound = true;
                                            //alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);

                                            if(numberOfSteps < stepsInCurrentOptimalPath)
                                            {
                                                stepsInCurrentOptimalPath = numberOfSteps;
                                            }

                                            firstDirectionInOptimalPath = firstDirection;

                                            //System.out.println("PATH FOUND, Steps: " + numberOfSteps + " Optimal path: " + stepsInCurrentOptimalPath + " dest: " + destinationX + "," + destinationY);

                                            //make sure this path is closed off i.e. make it a dead end unless a path reaches this tile with a fewer number of steps

                                            pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;

                                        }
                                        

                                        continue;
                                    }

                                
                                     
                                }
                                
                                else
                                    {
                                        //
                                    }
                                
                                    
                            }
                                
                                   
                            
                             //try to move EAST
                            
                            boolean isEastAvailable = !(byteContainsEast( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isEastAvailable) // checks if allowed to move to the east tile
                            {
                                if( (numberOfSteps + 1) < pathingNumberOfSteps2D[currentPosX + 1][currentPosY] || pathingNumberOfSteps2D[currentPosX + 1][currentPosY] == 0)
                                {
                                    //PathfinderTile eastTile = arrayPFTiles2D[currentPosX + 1][currentPosY];
                                    //System.out.println("east traverseed: " + pathingTilesTraversed[currentPosX + 1][currentPosY]);
                                    if( !pathingTilesTraversed[currentPosX + 1][currentPosY] ) // check if has traversed this tile this turn
                                    {
                                        //System.out.println("Moved East, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY + " 10,2 traverse: " + pathingArray2D[10][2]);
                                        //System.out.println("Tiles not avail: " + alPathsWhichAreDeadEnds.get(numberOfSteps));

                                        currentPosX += 1;        // updates the position in the array
                                        numberOfSteps++;                    // 
                                        lastDirectionTraveled = 2;

                                        currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                        pathingTilesTraversed[currentPosX][currentPosY] = true;
                                        //alTraversedTiles.add(currentPathFindertile);

                                        if(numberOfSteps == 1)
                                        {
                                            firstDirection = lastDirectionTraveled;
                                        }


                                        if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                        {
                                            pathFound = true;
                                            //alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                            firstDirectionInOptimalPath = firstDirection;

                                            if(numberOfSteps < stepsInCurrentOptimalPath)
                                            {
                                                stepsInCurrentOptimalPath = numberOfSteps;
                                            }
                                            //System.out.println("PATH FOUND, Steps: " + (alTraversedTiles.size() -1) +  " Optimal path: " + stepsInCurrentOptimalPath + " first direction: " + firstDirectionInOptimalPath + " dest: " + destinationX + "," + destinationY);

                                            //make sure this path is closed off i.e. make it a dead end
                                            pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;

                                        }

                                        continue;
                                     
                                    }
                                }

                                else // if unable to move east
                                    {
                                        
                                    }
                            }
   
                            
                            //try to move SOUTH
                            boolean isSouthAvailable = !(byteContainsSouth( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]));
                            if(isSouthAvailable) // checks if allowed to move to the south tile
                            {
                                if( (numberOfSteps + 1) < pathingNumberOfSteps2D[currentPosX][currentPosY + 1] || pathingNumberOfSteps2D[currentPosX][currentPosY + 1] == 0)
                                {
                                    //PathfinderTile southTile = arrayPFTiles2D[currentPosX][currentPosY + 1];

                                    if( !pathingTilesTraversed[currentPosX][currentPosY + 1] ) // check if has traversed this tile this turn
                                    {
                                        //System.out.println("Moved South, steps: " + numberOfSteps + " position: " + currentPosX + "," + currentPosY + " 10,2 traverse: " + pathingArray2D[10][2]);

                                        currentPosY += 1;        // updates the position in the array
                                        numberOfSteps++;                    // has taken one step
                                        lastDirectionTraveled = 4;

                                        if(numberOfSteps == 1)
                                        {
                                            firstDirection = lastDirectionTraveled;
                                        }

                                        currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                        pathingTilesTraversed[currentPosX][currentPosY] = true;
                                        //alTraversedTiles.add(currentPathFindertile);


                                        if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                        {
                                            pathFound = true;
                                            //alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                            firstDirectionInOptimalPath = firstDirection;

                                            if(numberOfSteps < stepsInCurrentOptimalPath)
                                            {
                                                stepsInCurrentOptimalPath = numberOfSteps;
                                            }
                                            //System.out.println("PATH FOUND, Steps: " + numberOfSteps + " Optimal path: " + stepsInCurrentOptimalPath + " first direction: " + firstDirectionInOptimalPath + " dest: " + destinationX + "," + destinationY);

                                            //make sure this path is closed off i.e. make it a dead end
                                            pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;


                                        }

                                        continue;

                                    }
                                }

                                else 
                                    {
                                        
                                    }
                            }
                               
   
                            //try to move WEST
                            boolean isWestAvailable = !(byteContainsWest( pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY] ));
                            if(isWestAvailable) // checks if allowed to move to the west tile
                            {
                                if( (numberOfSteps + 1) < pathingNumberOfSteps2D[currentPosX - 1][currentPosY] || pathingNumberOfSteps2D[currentPosX - 1][currentPosY] == 0)
                                {
                                    //PathfinderTile westTile = arrayPFTiles2D[currentPosX - 1][currentPosY];

                                    if( !pathingTilesTraversed[currentPosX - 1][currentPosY] ) // check if has traversed this tile this turn
                                    {
                                        //System.out.println("Moved West, steps: " + numberOfSteps+ " position: " + currentPosX + "," + currentPosY + " 10,2 traverse: " + pathingArray2D[10][2]);

                                        currentPosX -= 1;        // updates the position in the array
                                        numberOfSteps++;                    // has taken one step
                                        lastDirectionTraveled = 8;

                                        if(numberOfSteps == 1)
                                        {
                                            firstDirection = lastDirectionTraveled;
                                        }

                                        currentPathFindertile = arrayPFTiles2D[currentPosX][currentPosY];
                                        pathingTilesTraversed[currentPosX][currentPosY] = true;
                                        //alTraversedTiles.add(currentPathFindertile);


                                        if(currentPathFindertile.equals(destinationPathFindertile)) // if current tile is the destination tile
                                        {
                                            pathFound = true;
                                            //alArrayListsWithPathsWhichReachedDest.add(alTraversedTiles);
                                            firstDirectionInOptimalPath = firstDirection;

                                            if(numberOfSteps < stepsInCurrentOptimalPath)
                                            {
                                                stepsInCurrentOptimalPath = numberOfSteps;
                                            }
                                            //System.out.println("PATH FOUND, Steps: " + (alTraversedTiles.size() -1) + " Optimal path: " + stepsInCurrentOptimalPath + " first direction: " + firstDirectionInOptimalPath + " dest: " + destinationX + "," + destinationY + "\n===================================================================\n\n");

                                            //make sure this path is closed off i.e. make it a dead end
                                            pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;

                                        }

                                        continue;

                                    }
                                }

                                else // 
                                    {
                                        
                                    }
                            }
                                
                                
      
                            //If can move nowhere = DEAD END
                           
                           // check if not allowed to move anywhere
                           if((pathingArray2D[currentPosX][currentPosY] + prePathingArray2D[currentPosX][currentPosY]) == 15) // checks if not allowed to move to any tiles because they dead ends
                                {
                                    //System.out.println("Dead End: currentPos: " + currentPosX + "," + currentPosY);
                                    if(currentPosX == x && currentPosY == y)
                                    {
                                        //long executionTime = System.currentTimeMillis() - startTime;
                                        //System.out.println("pathing done, " + currentPosX + "," + currentPosY + " to " + destinationX + "," + destinationY +  " EXECUTION TIME: " + executionTime + " ms");
                                        
                                        isUniquePathsLeft = false;
                                        break;
                                    }
                                    //System.out.println("DEAD ENDsteps: " + numberOfSteps + "al total size: " + alPathsWhichAreDeadEnds.size() + " Al size == 4, last direction: " + lastDirectionTraveled + " current position: " + currentPosX + "," + currentPosY);
                                    if(lastDirectionTraveled == Pathfinder.DIRECTION_NORTH)
                                    {
                                        pathingArray2D[currentPosX][currentPosY + 1] += Pathfinder.DIRECTION_NORTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_EAST)
                                    {
                                        pathingArray2D[currentPosX - 1][currentPosY] += Pathfinder.DIRECTION_EAST;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_SOUTH)
                                    {
                                        pathingArray2D[currentPosX][currentPosY - 1] += Pathfinder.DIRECTION_SOUTH;
                                    }
                                    
                                    else if(lastDirectionTraveled == Pathfinder.DIRECTION_WEST)
                                    {
                                        pathingArray2D[currentPosX + 1][currentPosY] += Pathfinder.DIRECTION_WEST;
                                    }
                                    
                                    
                                    
                                    deadEndFound = true;
                                    continue;
                                }
                           
                           else // this means that we have nowhere to go because at least one tile has already been traversed this turn
                           {
                                if(currentPosX == x && currentPosY == y)
                                {
                                    //long executionTime = System.currentTimeMillis() - startTime;
                                    //System.out.println("pathing done, " + currentPosX + "," + currentPosY + " to " + destinationX + "," + destinationY +  " EXECUTION TIME: " + executionTime + " ms");
                                    isUniquePathsLeft = false;
                                    break;
                                }
                                pathingNumberOfSteps2D[currentPosX][currentPosY] = numberOfSteps;
                                //System.out.println("Dead end found, steps: " + numberOfSteps);
                                deadEndFound = true;
                                continue;
                                
                                
                           }

    
                           
                       } // and of the loop that goes through 1 path
                       
                      
                    } // end of isUniquePathsLeft loop (Loop that goes through all the paths)
                     
                     
                    //System.out.println("First direction: " + firstDirectionInOptimalPath);
                    assert firstDirectionInOptimalPath != 0 : "ERROR: firstdirection is 0, pathing error"; // if the direction is 0, then a path has not been found
                    directionsToDestination[destinationX][destinationY] = firstDirectionInOptimalPath;
                    //System.out.println("starting at: " + x + "," + y + " Destination: " + destinationX + "," + destinationY + " " + firstDirectionInOptimalPath + " and " + directionsToDestination[destinationX][destinationY]);
                    } // end of destination X loop
                   
                }

              arrayTiles2D[x][y].setDestinations(directionsToDestination);
              //System.out.println("Execution for 1 tile to all dests: " + (System.currentTimeMillis() - startTime1TileAllDests));
            }
            
            
            
        }
        
        
        
       
    }
    
    

}
